Counting sort

Performance:

Time: O(N);

Memory O(M), where M is a number of different elements

def count_sort(A):
    N = len(A)
    F = [0]*10                                 # 10 digits
    R = []
    for i in range(0, N):
        F[A[i]] += 1           # Frequency: [1, 2, 7, 2, 4, 2, 2, 1, 1, 1]
    for digit in range(0, 10):
        for i in range(F[digit]):
            R.append(digit)
    return R

# test

def test_sort(sort_algorithm):
    print("Testing: ", sort_algorithm.__doc__)
    print("testcase #1: ", end="")
    A = [1, 2, 3, 4, 5, 2, 4, 8, 4, 6, 2, 9, 0, 1, 2, 3, 4, 5, 6, 7, 2, 2, 2]
    A_sorted = [0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 7, 8, 9]
    R = count_sort(A)
    print("Ok" if R == A_sorted else "Fail")

if __name__ == "__main__":
    test_sort(count_sort)